Large scale terrain mapping is a difficult problem with wide-ranging applications, from space exploration to mining and more. For autonomous robots to function in such “high value” applications, it is important to have access to an efficient, flexible and high-fidelity representation of the operating environment. A digital representation of the operating environment in the form of a terrain model is typically generated from sensor measurements of the actual terrain at various locations within the operating environment. However, the data collected by sensors over a given area of terrain may be less than optimal, for a number of reasons. For example, taking many samples may be cost prohibitive, sensors may be unreliable or have poor resolution, or terrain may be highly unstructured. In other words, there may be uncertainty and/or incompleteness in data collected by sensors. Uncertainty and incompleteness are virtually ubiquitous in robotics as sensor capabilities are limited. The problem is magnified in a field robotics scenario due to the sheer scale of the application such as in a mining or space exploration scenario.
State of the art digital terrain representations generally map surfaces or elevations. However, they do not have a statistically sound way of incorporating and managing uncertainty. The assumption of statistically independent measurement data is a further limitation of many works that have used these approaches. While there are several interpolation techniques known, the independence assumption can lead to simplistic (simple averaging like) techniques that result in an inaccurate modelling of the terrain. Further, the limited perceptual capabilities of sensors renders most sensory data incomplete.
State of the art representations used in applications such as mining, space exploration and other field robotics scenarios as well as in geospatial engineering can be generally categorised as elevation maps, triangulated irregular networks (TIN's), contour models and their variants or combinations. Each approach has its own strengths and preferred application domains.
Grid based methods use a regularly spaced triangular, square (typical), rectangular or angular grid to represent space—the choice of the profile being dependent on the size of the area to be examined. A typical model would represent the elevation data corresponding to such a regularly spaced profile. The resulting representation would be a 2.5D representation of space. The main advantage of this representation is simplicity. The main limitations include the inability to handle abrupt changes, the dependence on the grid size, and the issue of scalability in large environments. In robotics, grid maps have been exemplified by numerous works, however the main weakness observed in most prior work in grid based representations is the lack of a statistically direct way of incorporating and managing uncertainty.
Triangulated Irregular Networks (TIN's) usually sample a set of surface specific points that capture all important aspects of the surface to be modelled—including bumps/peaks, troughs, breaks etc. The representation typically takes the form of an irregular network of such points (x,y,z) with each point having pointers to its immediate neighbours. This set of points is represented as a triangulated surface (the elemental surface is therefore a triangle). TINs are able to more easily capture sudden elevation changes and are also more flexible and efficient than grid maps in relatively flat areas. Overall, while this representation may be more scalable (from a surveyors perspective) than the grid representations, it may not handle incomplete data effectively—the reason being the assumption of statistical independence between data points. As a result of this, the elemental facet of the TIN—a triangle (plane)—may very well approximate the true nature of a “complicated” surface beyond acceptable limits. This however depends on the choice of the sensor and the data density obtained. It has been observed in the prior art that TiN's can be accurate and easily textured, with the main disadvantage being huge memory requirement which grows linearly with the number of scans. Piecewise linear approximations have been used to address this issue.
Other representations discussed in the prior art include probability densities, wavelets and contour based representations. The latter most represents the terrain as a succession of “isolines” of specific elevation (from minimum to maximum). They are naturally suited to model hydrological phenomena, however they require an order of magnitude more storage and do not provide any particular computational advantages.
There are several different kinds of interpolation strategies for grid data structures. The interpolation method basically attempts to find an elevation estimate by computing the intersection of the terrain with the vertical line at the point in the grid—this is done in image space rather than cartesian space. The choice of the interpolation method can have severe consequences on the accuracy of the model obtained.
The problems posed by large scale terrain mapping, associated with the size and characteristics of the data may also be present in other computer learning applications where data needs to be analysed and synthesised to create a model, forecast or other representation of the information on which the data is based.